package leetcode_100;

/**
 *@author 周杨
 *FirstMissingPositive_41 Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3
Example 2:

Input: [3,4,-1,1]
Output: 2
Example 3:

Input: [7,8,9,11,12]
Output: 1
 *describe:  用数组下标记录信息 哈希做法
 *2018年5月3日 下午3:15:57
 */
public class FirstMissingPositive_41 {

	public static void main(String[] args) {
		int nums[] =new int[] {1,1};
		
		System.out.println(firstMissingPositive(nums));
		for(int i:nums)
			System.out.println(i);
	}
	
	public static int firstMissingPositive(int[] nums) {
		if(nums.length==0)
			return 1;
		int temp;
		for(int i=0;i<nums.length;++i) {
			while(nums[i]!=i+1&&nums[i]>0&&nums[i]<=nums.length) {//移到这个数应该在的位置
				if(nums[i]==nums[nums[i]-1]) 
					break;
				else {
				temp=nums[i];//index
				nums[i]=nums[nums[i]-1];
				nums[temp-1]=temp;
				}
			}
		}
		int count=1;
		for(int i=0;i<nums.length;++i)
			if(nums[i]==count)
				++count;
        return count;
    }
}
